package week02

// 236. 二叉树的最近公共祖先
// https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	// 计算每个节点的父节点
	var parent = make(map[*TreeNode]*TreeNode)
	calcParent(root, nil, parent)
	// 标记root节点到p节点的路径
	var pParent = make(map[*TreeNode]struct{})
	for p != nil {
		pParent[p] = struct{}{}
		p = parent[p]
	}
	for {
		if _, ok := pParent[q]; ok {
			return q
		}
		q = parent[q]
	}
}

func calcParent(root, father *TreeNode, parent map[*TreeNode]*TreeNode) {
	if root == nil {
		return
	}
	parent[root] = father
	calcParent(root.Left, root, parent)
	calcParent(root.Right, root, parent)
}

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}